⟸ pàgina anterior ⟸

Exercici 2 (Tasca 2).

(regular languages, complement, minimization of DFAs)

El complementari d’un llenguatge regular és regular

Intercanviar estats finals i no finals en un DFA A produeix un nou DFA que reconeix el complementari del llenguatge reconegut per A.

1. Demostreu que L=\{aax\mid x\in\{a,b\}^*\} és un llenguatge regular. Construïu els DFAs mínims que reconeixen L i \overline{L}.

2. Demostreu que L=\{w \in \{a,b\}^* \mid |w|\in 3\mathbb N +1\} és un llenguatge regular. Construïu els DFAs mínims que reconeixen L i \overline{L}.

3. Demostreu que L=\{w \in \{0,1\}^* \mid \mathtt{value}_2(w)\in 3\mathbb N\} és un llenguatge regular. Construïu els DFAs mínims que reconeixen L i \overline{L}.

4. Donat un DFA A com a entrada, quin és el cost de calcular un DFA per \overline{L(A)}?

5. Si partíssim d’un DFA mínim, seria mínim el DFA obtingut per al complement?

6. Intercanviar estats finals i no finals en un NFA A produeix un NFA que reconeix el complement del llenguatge reconegut per A?